package LeetCode;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName DataStructure
 * @Description: TODO
 * @date ${DAT}10:17
 */
public class LeetCode19 {

    public class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }

    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;

        ListNode p = dummyHead;
        ListNode q = dummyHead;
        for (int i = 0; i < n + 1; i++){
            if (q != null){
                q = q.next;
            }
        }
        //此时q和p相差n+1步，之间相隔n个节点
        while (q != null){
            p = p.next;
            q = q.next;
        }
        //此时p指针就是待删除节点的前一个节点
        p.next = p.next.next;
        return dummyHead.next;
    }
}
